package codetop;

import java.util.*;
import java.util.Map;

public class LRU3 {
    public static void main(String[] args) {

    }
    static class Node {
        int key, value;
        Node left, right;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    static class LRUCache {
        int capacity;
        Node head, tail;
        Map<Integer, Node> map;
        public LRUCache(int capacity) {
            this.capacity = capacity;
            head = new Node(-1, -1);
            tail = new Node(-1, -1);
            head.right = tail;
            tail.left = head;
            map = new HashMap<>();
        }
        public void refresh(Node node){
            delete(node);
            node.right = head.right;
            head.right = node;
            node.left = head;
            node.right.left = node;
        }
        public void delete(Node node){
            if(node.left != null){
                node.left.right = node.right;
                node.right.left = node.left;
            }
        }
        public int get(int key) {
           if(map.containsKey(key)){
               refresh(map.get(key));
               return map.get(key).value;
           }
           else
               return -1;
        }

        public void put(int key, int value) {
            Node n = null;
            if(map.containsKey(key)){
                n = map.get(key);
                n.value = value;
            }
            else {
                if(map.size() == capacity){
                    Node del = tail.left;
                    map.remove(del.key);
                    delete(del);
                }
                n = new Node(key,value);
                map.put(key,n);
            }
            refresh(n);
        }
    }
}
